import functools


class Solution(object):
    def shortestCommonSupersequence(self, str1, str2):
        n1 = len(str1)
        n2 = len(str2)
        @functools.cache
        def dfs(m, n):
            if m == 0 or n == 0:
                return 0, -1, -1
            else:
                if str1[m - 1] == str2[n - 1]:
                    return dfs(m - 1, n - 1)[0] + 1, m - 1, n - 1
                else:
                    l1, p1, q1 = dfs(m - 1, n)
                    l2, p2, q2 = dfs(m, n - 1)
                    if l1 > l2:
                        return l1, p1, q1
                    else:
                        return l2, p2, q2
        _, p, q = dfs(n1, n2)
        ans = []
        while p != -1:
            if str1[p] == str2[q]:
                ans.append([p, q])
            _, p, q = dfs(p, q)
        ans.reverse()
        out = []
        left0 = 0
        left1 = 0
        for index1, index2 in ans:
            while left0 < index1:
                out.append(str1[left0])
                left0 += 1
            while left1 < index2:
                out.append(str2[left1])
                left1 += 1
            out.append(str1[index1])
            left0 = index1 + 1
            left1 = index2 + 1
        while left0 < n1:
            out.append(str1[left0])
            left0 += 1
        while left1 < n2:
            out.append(str2[left1])
            left1 += 1
        return ''.join(out)


data = Solution()
str1 = "abac"
str2 = "cab"
print(data.shortestCommonSupersequence(str1, str2))